Zero Knowledge Proof
Proving a proposition of "knowing a fact" without revealing its content is achieved through a technique called "Zero-Knowledge Proof" or ZKP. In cryptography, ZKP allows one person to prove the truth of a proposition (usually a mathematical one) to another person without revealing any knowledge other than the fact itself. This method involves a series of interactions between the prover and the verifier, where the prover convinces the verifier of the truth of the proposition without revealing any additional information. More information about ZKP can be found on ゼロ知識証明 - Wikipedia and Old technology: Zero-knowledge interactive proof - Qiita.
To successfully perform a ZKP, certain conditions must be met:
1. The questioner must know the correct answer.
2. If the questioner knows the correct answer, proving it becomes easier.
3. Brute-force methods are practically impossible due to the exponential computational complexity.
In the context of ZKP, it is easier to transform a problem into a different form, where knowing the correct answer to the transformed problem also reveals the correct answer to the original problem. This concept is similar to the concept of a Common Divisor. Additionally, the transformation rules between the original problem and the transformed problem are not easily discernible. Even if the correct answer to the transformed problem is known, without knowledge of the transformation rules, the correct answer to the original problem cannot be determined. When these conditions are met, ZKP becomes possible.
ZKP originated from the Interactive Proof System model, which is a variant of the NP proof system. The NP proof system is limited to deterministic algorithms that verify the correctness of a problem based on evidence provided by the prover. By extending this system to probabilistic algorithms, higher expressive power can be achieved. However, it is still uncertain whether NP is a proper subset of IP. More information about this can be found in Motivation for Dialogue Proof Systems - Cryptography Study Group.
ZKP has various applications, including Authentication, Digital Signature, and solving scalability issues in Ethereum transactions. It is often used in Zk-Rollup for scalability purposes. Another commonly used technique is zk-SNARK. For more details, refer to Zero-knowledge proof is good.
For further reading and references on Zero Knowledge Proof, please refer to Explanation of Cryptography Series 'Zero Knowledge Proof' - Qiita.